package main

import "fmt"

var lcmAB, lcmAC, lcmBC, lcmABC int

func lcm(a, b int) int {
	final := a * b
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return final / a
}

func nUnderIt(num, a, b, c int) int {
	return (num/a + num/b + num/c) - (num/lcmAB + num/lcmAC + num/lcmBC) + num/lcmABC
}

func nthUglyNumber(n int, a int, b int, c int) int {
	lcmAB = lcm(a, b)
	lcmAC = lcm(a, c)
	lcmBC = lcm(b, c)
	lcmABC = lcm(lcmAB, c)
	fmt.Println(lcmAB, lcmAC, lcmBC, lcmABC)
	left, right := 1, int(2e9)
	for left <= right {
		mid := (left + right) >> 1
		if nUnderIt(mid, a, b, c) < n {
			left = mid + 1
		} else {
			right = mid - 1
		}
		fmt.Println(left, mid, right)
		if mid == 1999999982 {
			fmt.Println(nUnderIt(mid, a, b, c))
		}

	}
	return left
}

func main() {
	res := nthUglyNumber(1000000000, 2, 217983653, 336916467)
	fmt.Println(res)
}
